﻿//https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-100-liked

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int& p, int inbegin, int inend)
    {
        if (inbegin > inend)
            return NULL;

        //创建根节点
        TreeNode* root = new TreeNode(preorder[p]);

        //区分左右子树
        int rooti = inbegin;
        while (rooti <= inend)
        {
            if (preorder[p] == inorder[rooti])
            {
                break;
            }
            else
            {
                rooti++;
            }
        }
        p++;
        //递归创建左右子树
        root->left = build(preorder, inorder, p, inbegin, rooti - 1);
        root->right = build(preorder, inorder, p, rooti + 1, inend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        //记录根节点
        int i = 0;
        TreeNode* root = build(preorder, inorder, i, 0, inorder.size() - 1);
        return root;
    }
};